package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 动态规划算法示例
 * 
 * @author csy
 * @description 通过实例详细讲解动态规划的基本概念和应用
 * 
 *              动态规划核心要素：
 *              1. 最优子结构：问题的最优解包含子问题的最优解
 *              2. 重叠子问题：子问题会重复出现
 *              3. 状态转移方程：描述问题结构的数学表达式
 * 
 *              常见解题步骤：
 *              1. 定义状态：明确dp数组的含义
 *              2. 找出状态转移方程：思考如何从子问题推导出当前问题的解
 *              3. 确定初始条件和边界条件
 *              4. 确定计算顺序：自底向上或自顶向下
 */
public class DynamicProgrammingExamples {

    /**
     * 示例1：斐波那契数列
     * 
     * 问题描述：
     * 求斐波那契数列的第n个数，F(n) = F(n-1) + F(n-2)，其中 F(0) = 0, F(1) = 1
     * 
     * 详细解析：
     * 1. 为什么用动态规划？
     * - 存在重叠子问题：计算F(4)需要F(3)和F(2)，计算F(3)又需要F(2)，F(2)被重复计算
     * - 具有最优子结构：F(n)可以由F(n-1)和F(n-2)直接得到
     * 
     * 2. 解题步骤：
     * a) 定义状态：dp[i]表示第i个斐波那契数
     * b) 状态转移方程推导：
     * dp[i] = dp[i-1] + dp[i-2]
     * 推导原理：
     * - 根据斐波那契数列的定义，每个数都是前两个数的和
     * - 这个性质直接反映在状态转移方程中
     * - 例如：要得到F(4)
     * 1) F(4) = F(3) + F(2)
     * 2) F(3) = F(2) + F(1)
     * 3) F(2) = F(1) + F(0)
     * 所以dp[i]必须等于dp[i-1] + dp[i-2]
     * 
     * c) 初始状态：dp[0] = 0, dp[1] = 1
     * d) 计算顺序：从小到大，因为大的数依赖小的数
     * 
     * 3. 优化思路：
     * - 可以只用两个变量存储前两个状态，将空间复杂度优化到O(1)
     * - 可以使用矩阵快速幂优化时间复杂度到O(logn)
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static long fibonacci(int n) {
        if (n <= 1)
            return n;

        // 定义dp数组，存储每个位置的斐波那契数
        long[] dp = new long[n + 1];
        // 设置初始状态
        dp[0] = 0;
        dp[1] = 1;

        // 根据状态转移方程计算后续值
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    /**
     * 示例2：零钱兑换
     * 
     * 问题描述：
     * 给定不同面额的硬币coins和总金额amount，求凑成总金额所需的最少硬币个数
     * 
     * 详细解析：
     * 1. 为什么用动态规划？
     * - 存在重叠子问题：计算amount=11时，可能多次计算amount=5的情况
     * - 具有最优子结构：最少硬币数可以由更小金额的最优解推导出来
     * 
     * 2. 解题步骤：
     * a) 定义状态：dp[i]表示凑成金额i所需的最少硬币个数
     * b) 状态转移方程推导：
     * dp[i] = min(dp[i], dp[i-coin] + 1) for coin in coins
     * 推导原理：
     * 1) 对于金额i，我们可以使用任意一个面值小于等于i的硬币
     * 2) 如果使用面值为coin的硬币：
     * - 需要先凑出金额i-coin（这就是dp[i-coin]）
     * - 然后加上这个面值为coin的硬币（这就是+1）
     * 3) 例如：要凑出金额5，硬币有[1,2,5]
     * - 使用面值1：dp[5] = dp[4] + 1
     * - 使用面值2：dp[5] = dp[3] + 1
     * - 使用面值5：dp[5] = dp[0] + 1
     * 最终取这三种情况的最小值
     * 
     * c) 初始状态：dp[0] = 0，其他位置初始化为一个较大值
     * d) 遍历顺序：
     * - 外层遍历金额：保证每个金额都被考虑
     * - 内层遍历硬币：尝试使用每种面额
     * 
     * 时间复杂度：O(amount * coins.length)
     * 空间复杂度：O(amount)
     */
    public static int coinChange(int[] coins, int amount) {
        // 定义dp数组，初始化为一个较大值
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        // 设置初始状态
        dp[0] = 0;

        // 遍历每个金额
        for (int i = 1; i <= amount; i++) {
            // 尝试使用每个硬币
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 如果dp[amount]仍然是初始值，说明无解
        return dp[amount] > amount ? -1 : dp[amount];
    }

    /**
     * 示例3：最长公共子序列 (LCS)
     * 
     * 问题描述：
     * 给定两个字符串，求它们的最长公共子序列的长度
     * 
     * 详细解析：
     * 1. 为什么用动态规划？
     * - 存在重叠子问题：较长序列的LCS包含较短序列的LCS
     * - 具有最优子结构：当前LCS长度可以由子问题的LCS推导
     * 
     * 2. 解题步骤：
     * a) 定义状态：dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度
     * b) 状态转移方程推导：
     * 当text1[i-1] == text2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1
     * 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
     * 
     * 推导原理：
     * 1) 当前字符相同时（text1[i-1] == text2[j-1]）：
     * - 这个字符一定在LCS中
     * - 所以当前LCS长度等于去掉这两个字符后的LCS长度加1
     * 例如：text1="abc", text2="ac"
     * 比较到c和c时，它们相同，所以dp[3][2] = dp[2][1] + 1
     * 
     * 2) 当前字符不同时：
     * - 当前字符至少有一个不在LCS中
     * - 需要考虑两种情况：
     * a. 不使用text1的当前字符：dp[i-1][j]
     * b. 不使用text2的当前字符：dp[i][j-1]
     * - 取这两种情况的最大值
     * 例如：text1="abd", text2="ac"
     * 比较到d和c时，它们不同，所以dp[3][2] = max(dp[2][2], dp[3][1])
     * 
     * c) 初始状态：dp[0][j] = dp[i][0] = 0
     * 
     * 时间复杂度：O(m*n)
     * 空间复杂度：O(m*n)
     */
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // 定义dp数组，初始值默认为0
        int[][] dp = new int[m + 1][n + 1];

        // 遍历两个字符串的每个字符
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 字符相同，LCS长度加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 字符不同，取两种情况的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }

    /**
     * 示例4：0-1背包问题
     * 
     * 问题描述：
     * 给定n个物品，每个物品有重量和价值两个属性。在总重量不超过背包容量的情况下，求放入物品的最大价值
     * 
     * 详细解析：
     * 1. 为什么用动态规划？
     * - 存在重叠子问题：选择不同物品组合时会重复计算
     * - 具有最优子结构：当前状态的最优解可以由子问题的最优解推导
     * 
     * 2. 解题步骤：
     * a) 定义状态：dp[i][w]表示前i个物品放入容量为w的背包的最大价值
     * b) 状态转移方程推导：
     * dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
     * 
     * 推导原理：
     * 1) 对于第i个物品，我们面临两个选择：放或不放
     * 2) 不放入第i个物品时：
     * - 直接继承前i-1个物品的最优解：dp[i-1][w]
     * - 背包容量不变
     * 
     * 3) 放入第i个物品时：
     * - 需要先腾出物品i的重量：w-weight[i]
     * - 在剩余容量下，考虑前i-1个物品的最优解：dp[i-1][w-weight[i]]
     * - 加上物品i的价值：value[i]
     * 
     * 4) 例如：对于物品重量为3、价值为4的物品：
     * - 不放入：保持原状态dp[i-1][w]
     * - 放入：dp[i-1][w-3] + 4
     * 最终取两种情况的最大值
     * 
     * c) 初始状态：dp[0][w] = 0
     * 
     * 3. 优化思路：
     * - 可以使用一维数组优化空间复杂度
     * - 需要逆序遍历重量，防止物品被重复使用
     * 
     * 时间复杂度：O(n*W)
     * 空间复杂度：O(n*W)
     */
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        // 定义dp数组
        int[][] dp = new int[n + 1][capacity + 1];

        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 遍历每个容量
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    // 可以放入物品i，取放入和不放入的最大值
                    dp[i][w] = Math.max(
                            dp[i - 1][w], // 不放入
                            dp[i - 1][w - weights[i - 1]] + values[i - 1] // 放入
                    );
                } else {
                    // 不能放入物品i，继承之前的结果
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][capacity];
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试斐波那契数列
        System.out.println("=== 斐波那契数列测试 ===");
        int[] fibTests = { 0, 1, 2, 3, 4, 5, 6, 7 };
        for (int n : fibTests) {
            System.out.printf("F(%d) = %d%n", n, fibonacci(n));
        }

        // 测试零钱兑换
        System.out.println("\n=== 零钱兑换测试 ===");
        int[] coins = { 1, 2, 5 };
        int amount = 11;
        System.out.printf("凑成金额%d的最少硬币数：%d%n",
                amount, coinChange(coins, amount));

        // 测试最长公共子序列
        System.out.println("\n=== 最长公共子序列测试 ===");
        String text1 = "abcde", text2 = "ace";
        System.out.printf("字符串\"%s\"和\"%s\"的最长公共子序列长度：%d%n",
                text1, text2, longestCommonSubsequence(text1, text2));

        // 测试背包问题
        System.out.println("\n=== 背包问题测试 ===");
        int[] weights = { 2, 3, 4, 5 };
        int[] values = { 3, 4, 5, 6 };
        int capacity = 8;
        System.out.printf("背包容量为%d时的最大价值：%d%n",
                capacity, knapsack(weights, values, capacity));
    }

    /**
     * 打印dp数组状态（用于调试和理解dp数组的变化过程）
     */
    private static void printDpMatrix(int[][] dp) {
        System.out.println("DP矩阵状态：");
        for (int[] row : dp) {
            System.out.println(Arrays.toString(row));
        }
        System.out.println();
    }
}